1. Field of the Invention
The present invention relates to a priority encoder for a content addressable memory (CAM) array.
2. Discussion of Related Art
CAM cells are defined as memory cells that are addressed in response to their content, rather than by a physical address within an array. FIG. 1 is a block diagram of a conventional memory array formed using twelve CAM cells. The CAM cells are labeled M.sub.X,Y, where X is the row of the array, and Y is the column of the array. Thus, the array includes CAM cells M.sub.0,0 to M.sub.2,3. Each of the CAM cells is programmed to store a data bit value. In the described example, the data bit value stored in each CAM cell is indicated by either a "0" or a "1" in brackets. For example, CAM cells M.sub.0,0, M.sub.0,1, M.sub.0,2 and M.sub.0,3 store data bit values of 0, 1, 0 and 0, respectively. Each row of CAM cells is coupled to a common match line. For example, CAM cells M.sub.0,0, M.sub.0,1, M.sub.0,2 and M.sub.0,3 are coupled to match line MATCH.sub.0.
The array of CAM cells is addressed by providing a data bit value to each column of CAM cells. Thus data bit values D.sub.0, D.sub.1, D.sub.2 and D.sub.3 are provided to columns 0, 1, 2 and 3, respectively. Note that complementary data bit values D.sub.0 #, D.sub.1 #, D.sub.2 # and D.sub.3 # are also provided to columns 0, 1, 2 and 3, respectively. If the data bit values stored in a row of the CAM cells match the applied data bit values D.sub.0 -D.sub.3, then a match condition occurs. For example, if the data bit values D.sub.0, D.sub.1, D.sub.2 and D.sub.3 are 0, 1, 0 and 0, respectively, then the data bit values stored in the CAM cells of row 0 match the applied data bit values. Under these conditions, the MATCH.sub.0 signal is asserted true (e.g., high). Because the applied data bit values D.sub.0, D.sub.1, D.sub.2 and D.sub.3 do not match the data bit values store in the CAM cells of rows 1 or 2, the MATCH.sub.1 and MATCH.sub.2 signals are de-asserted false (e.g., low). The match signals MATCH.sub.0 -MATCH.sub.2 can be used for various purposes, such as implementing virtual addressing, in a manner known to those skilled in the art.
FIG. 2 is a block diagram of a conventional CAM System 1 that includes a 64 Kbit CAM array 10 and an associated priority encoder 11. CAM array 10 includes 1024 rows and 64 columns of CAM cells. A 64-bit data input signal D[63:0] is provided from an input/output (I/O) circuit (not shown) to CAM array 10. Each row of CAM cells in CAM array 10 simultaneously compares its contents with the input data signal D[63:0] in the manner described above in connection with FIG. 1. If a match is detected in any of the rows, CAM array 10 asserts a corresponding match control signal. More specifically, if a match is detected in row N of CAM array 10, then match control signal MATCH_N is asserted, where N is an integer between 0 and 1023.
More than one of the match control signals can be asserted during a comparison operation. For example, match control signals MATCH_1, MATCH_125 and MATCH_1000 may be asserted during the same comparison operation. All of the match control signals are provided to priority encoder 11. Priority encoder 11 determines which one of the asserted match control signals has priority. In response, priority encoder 11 provides a 10-bit output address A[9:0] that corresponds with the asserted match control signal determined to have priority. The output address A[9:0] is provided to the I/O circuitry (not shown).
FIG. 3 is a block diagram of a 1 Mbit CAM system 100 that includes sixteen CAM arrays 101-116 identical to CAM array 10 (FIG. 2). Each of the sixteen CAM arrays 101-116 receives the input data signal D[63:0] and simultaneously generates the appropriate match control signals. Priority encoder 120 receives the match control signals from all of the CAM arrays 101-116. In response, priority encoder 120 generates a 14-bit output address A[13:0].
CAM system 100 consumes a significant amount of power. In general, CAM arrays 101-116 consume about 2.5 Watts. Priority encoder 120 also typically consumes about 2.5 Watts. The I/O circuitry associated with CAM system 100 consumes about 1 Watt. This is a significant amount of power to be consumed by a memory system. Consequently, CAM arrays are typically limited to smaller capacities than 1 Mbit (e.g., 1 Kbit).
It would therefore be desirable to have a CAM system having a relatively large capacity, but which consumes less power than a conventional CAM system having the same capacity.